package NewCoder;

import java.util.PriorityQueue;
import java.util.Random;

public class BM48 {
    PriorityQueue<Integer> A=new PriorityQueue<>();//存储较大元素的小根堆
    PriorityQueue<Integer> B=new PriorityQueue<>((x,y)->(y-x));//存储较小元素的大根堆

    public void Insert(Integer num) {
        if(A.size()==B.size()){
            B.offer(num);
            A.offer(B.poll());
        }else{
            A.add(num);
            B.add(A.poll());
        }
    }

    public Double GetMedian() {
        return A.size()!=B.size()?(double)A.peek():(double)(A.peek()+B.peek())/2;
    }
}
